/LMAR=0/XLINE=3/FONT#0=BAXL30/FONT#1=BAXM30/FONT#2=BASB30/FONT#3=SUB/FONT#4=SUP/FONT#5=BASL35/FONT#6=NGR25/FONT#7=MATH30/FONT#8=FIX25/FONT#9=GRKB30
␈↓ α∧␈↓␈↓ u1


␈↓ α∧␈↓CS206␈↓ ¬TMIDTERM EXAMINATION␈↓ 
lFALL 1981 

␈↓ α∧␈↓␈↓ αTThis␈α
examination␈α∞is␈α
open␈α
book␈α∞and␈α
notes.␈α∞ Write␈α
LISP␈α
functions␈α∞or␈α
predicates␈α∞as␈α
follows
␈↓ α∧␈↓except where something else is requested.  Either notation may be used.

␈↓ α∧␈↓1.␈α␈↓↓balanced␈αx␈↓␈αis␈αtrue␈αif␈αthe␈αS-expression␈α␈↓↓x␈↓␈αis␈αeither␈αatomic␈αor␈αhas␈αbalanced␈α␈↓↓car␈↓␈αand␈α␈↓↓cdr␈↓␈αparts␈αand
␈↓ α∧␈↓the␈α
depths␈αof␈α
the␈α␈↓↓car␈↓␈α
and␈α
␈↓↓cdr␈↓␈αparts␈α
differ␈αby␈α
no␈αmore␈α
than␈α
one.␈α (The␈α
depth␈αof␈α
an␈αS-expression␈α
is
␈↓ α∧␈↓the length of the longest ␈↓↓car-cdr␈↓ chain from the top to an atom).

␈↓ α∧␈↓2. Prove that for all S-expressions ␈↓↓x␈↓ and ␈↓↓z␈↓ and atoms ␈↓↓y␈↓,

␈↓ α∧␈↓␈↓ αT␈↓↓subst[x,y,subst[x,y,z]] = subst[subst[x,y,x],y,z]␈↓.

␈↓ α∧␈↓␈↓↓subst␈↓,␈α
which␈α
substitutes␈α
the␈α
S-expression␈α
␈↓↓x␈↓␈α
for␈α
each␈α
occurrence␈α
of␈α
the␈α
atom␈α
␈↓↓y␈↓␈α
in␈α
the␈αS-expression␈α
␈↓↓z␈↓
␈↓ α∧␈↓is defined by

␈↓ α∧␈↓␈↓ αT␈↓↓subst[x,y,z] ← ␈↓αif␈↓↓ ␈↓αa␈↓↓t z ␈↓αthen␈↓↓ [␈↓αif␈↓↓ z = y ␈↓αthen␈↓↓ x ␈↓αelse␈↓↓ z] ␈↓αelse␈↓↓ subst[x,y,␈↓αa␈↓↓ z].subst[x,y,␈↓αd␈↓↓ z]␈↓.

␈↓ α∧␈↓Be sure and indicate the ␈↓	F␈↓ used in the induction.

␈↓ α∧␈↓3.␈α
Boolean␈α∞expressions␈α
may␈α
be␈α∞built␈α
up␈α∞from␈α
atoms␈α
using␈α∞the␈α
forms␈α∞(AND␈α
␈↓↓p␈α
q␈↓),␈α∞(OR␈α
␈↓↓p␈α∞q␈↓)␈α
and
␈↓ α∧␈↓(NOT␈α
␈↓↓p␈↓).␈α
 ␈↓↓ificate␈αe␈↓␈α
is␈α
the␈α
result␈αof␈α
converting␈α
the␈α
Boolean␈αexpression␈α
␈↓↓e␈↓␈α
to␈α
a␈αconditional␈α
expression
␈↓ α∧␈↓according to the rules

␈↓ α∧␈↓␈↓ αT(AND ␈↓↓p q␈↓) → (IF ␈↓↓p q␈↓ F),

␈↓ α∧␈↓␈↓ αT(OR ␈↓↓p q␈↓) → (IF ␈↓↓p␈↓ T ␈↓↓q␈↓),

␈↓ α∧␈↓and

␈↓ α∧␈↓␈↓ αT(NOT ␈↓↓p␈↓) → (IF ␈↓↓p␈↓ F T).

␈↓ α∧␈↓␈↓ αTa. Write the function ␈↓↓ificate␈↓.

␈↓ α∧␈↓␈↓ αTb.␈α∞Write␈α∞␈↓↓ificate1␈α∂e␈↓␈α∞which␈α∞converts␈α∞expressions␈α∂containing␈α∞ANDs␈α∞and␈α∞ORs␈α∂with␈α∞arbitrary
␈↓ α∧␈↓numbers of arguments.

␈↓ α∧␈↓4.␈α∂␈↓↓flip␈α∞u␈↓␈α∂interchanges␈α∞the␈α∂first␈α∞and␈α∂second␈α∞elements␈α∂of␈α∞a␈α∂list,␈α∞the␈α∂third␈α∞and␈α∂fourth,␈α∞etc.␈α∂ If␈α∞the
␈↓ α∧␈↓number of elements is odd, the last is left as is.  Thus

␈↓ α∧␈↓␈↓ αT␈↓↓flip␈↓ (A B C D E) = (B A D C E).

␈↓ α∧␈↓␈↓ αTa. Write ␈↓↓flip␈↓.

␈↓ α∧␈↓␈↓ αTb. Prove that for all lists ␈↓↓u␈↓,

␈↓ α∧␈↓␈↓ αT␈↓↓flip flip u = u␈↓.

␈↓ α∧␈↓Be sure and indicate the kind of induction and the ␈↓	F␈↓ used in the induction statement.